
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Main {

    /*给定两个整数数组 inorder 和 postorder ，
    其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树 。*/
    public TreeNode buildTree(int[] inorder , int[] postorder) {
        return buildTreeHelper( inorder, postorder, postorder.length-1, 0, inorder.length - 1);
    }

    private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int postStart, int inStart, int inEnd) {
        if (postStart <0 || postStart > postorder.length - 1 || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postStart]);

        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
                break;
            }
        }

        root.right = buildTreeHelper(inorder, postorder, postStart-1,inIndex + 1, inEnd);
        root.left = buildTreeHelper(inorder, postorder, postStart - (inEnd - inIndex) - 1,inStart, inIndex - 1);
        return root;
    }

    /*给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。*/
    public String tree2str(TreeNode root) {
        if(root==null) return null;

        StringBuilder sb = new StringBuilder();

        tree2strHelper(root, sb);
        return sb.toString();
    }

    private void tree2strHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }

        sb.append(root.val);

        if (root.left != null || root.right != null) {
            sb.append("(");
            tree2strHelper(root.left, sb);
            sb.append(")");
        }

        if (root.right != null) {
            sb.append("(");
            tree2strHelper(root.right, sb);
            sb.append(")");
        }
    }

    public String tree2str2(TreeNode root) {
        StringBuffer ans = new StringBuffer();
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        stack.push(root);
        Set<TreeNode> visited = new HashSet<TreeNode>();
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (!visited.add(node)) {
                if (node != root) {
                    ans.append(")");
                }
                stack.pop();
            } else {
                if (node != root) {
                    ans.append("(");
                }
                ans.append(node.val);
                if (node.left == null && node.right != null) {
                    ans.append("()");
                }
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
        return ans.toString();
    }

/*给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
* 要求使用 非递归 的方法
* */

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    }
    /*给定一个二叉树的根节点 root ，返回 它的 中序 遍历。*/

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }

        return result;
    }
    /*给定一个二叉树的根节点 root ，返回 它的 后序 遍历。*/
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode lastVisited = null;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            TreeNode peekNode = stack.peek();

            if (peekNode.right == null || peekNode.right == lastVisited) {
                result.add(peekNode.val);
                lastVisited = stack.pop();
            } else {
                curr = peekNode.right;
            }
        }

        return result;
    }
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}